package com.sicheng.lc.周赛.分类.前缀和or差分数组;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/10/9 20:21
 */
public class 沙漏的最大总和 {
    //https://leetcode.cn/problems/maximum-sum-of-an-hourglass/
    public int maxSum(int[][] g) {
        int m = g.length, n = g[0].length;
        int[][] s = new int[m + 1][n + 1];

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                s[i][j] += g[i - 1][j - 1] + s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1];
            }
        }

        int max = 0;

        for (int i = 1; i <= m - 2; i++) {
            for (int j = 1; j <= n - 2; j++) {
                max = Math.max(max, s[i + 2][j + 2] + s[i - 1][j - 1] - s[i + 2][j - 1] - s[i - 1][j + 2] - g[i][j - 1] - g[i][j + 1]);
            }
        }


        return max;
    }

    public static void main(String[] args) {
        沙漏的最大总和 s = new 沙漏的最大总和();
        int[][] g = {
                {6, 2, 1, 3},
                {4, 2, 1, 5},
                {9, 2, 8, 7},
                {4, 1, 2, 9}
        };

        Integer x = 9;
        System.out.println(s.maxSum(g));
    }
}
